Neural Information Processing Systems http://nips.cc/

Extending related recent work, we give a full semi-algebraic description of the set of covariance matrices of any such model.

Paper Summary: The paper presents a technique for testing whether a given set of samples are drawn from a postulated Gaussian latent tree model or a saturated Gaussian graphical model. The paper first characterizes a set of necessary and sufficient constraints that any covariance matrix of a Gaussian latent tree model should satisfy. It then uses these constraints to come up with a test statistic. The paper extends past work on testing for Gaussian latent tree models to settings where the observed variables are allowed to have degree up to 2. The test statistic presented in the paper is based on gaussian approximation for maxima of high dimensional sums. Simulations suggest that the test statistic can potentially work in high dimensional settings.

We consider general Gaussian latent tree models in which the observed variables are not restricted to be leaves of the tree. Extending related recent work, we give a full semi-algebraic description of the set of covariance matrices of any such model. In other words, we find polynomial constraints that characterize when a matrix is the covariance matrix of a distribution in a given latent tree model. However, leveraging these constraints to test a given such model is often complicated by the number of constraints being large and by singularities of individual polynomials, which may invalidate standard approximations to relevant probability distributions. Illustrating with the star tree, we propose a new testing methodology that circumvents singularity issues by trading off some statistical estimation efficiency and handles cases with many constraints through recent advances on Gaussian approximation for maxima of sums of high-dimensional random vectors. Our test avoids the need to maximize the possibly multimodal likelihood function of such models and is applicable to models with larger number of variables. These points are illustrated in numerical experiments.

We consider general Gaussian latent tree models in which the observed variables are not restricted to be leaves of the tree. Extending related recent work, we give a full semi-algebraic description of the set of covariance matrices of any such model. In other words, we find polynomial constraints that characterize when a matrix is the covariance matrix of a distribution in a given latent tree model. However, leveraging these constraints to test a given such model is often complicated by the number of constraints being large and by singularities of individual polynomials, which may invalidate standard approximations to relevant probability distributions. Illustrating with the star tree, we propose a new testing methodology that circumvents singularity issues by trading off some statistical estimation efficiency and handles cases with many constraints through recent advances on Gaussian approximation for maxima of sums of high-dimensional random vectors. Our test avoids the need to maximize the possibly multimodal likelihood function of such models and is applicable to models with larger number of variables. These points are illustrated in numerical experiments.

Latent tree models are graphical models defined on trees, in which only a subset of variables is observed. They were first discussed by Judea Pearl as tree-decomposable distributions to generalise star-decomposable distributions such as the latent class model. Latent tree models, or their submodels, are widely used in: phylogenetic analysis, network tomography, computer vision, causal modeling, and data clustering. They also contain other well-known classes of models like hidden Markov models, Brownian motion tree model, the Ising model on a tree, and many popular models used in phylogenetics. We offer here a concise introduction to the theory of latent tree models. We emphasise the role of tree metrics in the structural description of this model class, in designing learning algorithms, and in understanding fundamental limits of what and when can be learned. We present Gaussian and general Markov models as subclasses of latent tree models that admits tractable and rigorous analysis. A leaf of T is a vertex of degree one, an internal vertex is a vertex which is not a leaf, and an inner edge is an edge whose both ends are internal vertices. Given a treeT define a rooted tree as a directed graph obtained from T by picking one of its verticesr and directing all edges away fromr . The vertexr is called the root. Trees will be always leaf-labeled with the labelling set{ 1,...,m}, where m is the number of leaves. An undirected tree is trivalent if each internal vertex has degree precisely three. A rooted tree is a binary rooted tree if each internal vertex has precisely two children. In many applications rooted trees are depicted without using arrows, where direction is made implicit by drawing the root on the top and the leaves on the bottom; see Figure 1(c). Two special types of undirected trees are: a star tree with one internal vertex and a trivalent tree on four leaves called a quartet tree; see Figure 1(a) and (b). A forest is a collection of trees. Forests here are also leaf-labeled with the labelling set is{ 1,...,m}, which means that each tree in this collection is leaf-labeled and the corresponding collection of labelling sets forms a set partition of { 1,...,m}. We define three graph operations on trees (forests). Removing an edge means removing that edge from the edge set. Contracting an edge u v means removingu,v from the vertex set, adding a new vertexw and edges such thatw is adjacent to all vertices which were adjacent tou or v. Suppressing a vertex of degree two means removing that vertex and replacing the two edges incident to that vertex by a single edge. 1 2 3 4 5 1 2 3 4 (a) (b) (c) Figure 1: (a) An undirected star tree with five leaves, (b) a quartet tree, (c) a binary rooted tree.